#include <stdio.h>

#define N 15
#define M 15
#define MAX(x, y) ((x) > (y) ? (x) : (y))

int g_v[N][M] = { 0 };

void dfs(int** grid, int gridSize, int* gridColSize, int x, int y, int gold, int *result)
{
    if (grid[y][x] == 0) {
        return;
    }

    gold += grid[y][x];
    *result = MAX(*result, gold);

    g_v[y][x] = 1;
    int dx[] = { 1, -1, 0, 0 };
    int dy[] = { 0, 0, 1, -1 };
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (xx < 0 || xx >= gridColSize[0] || yy < 0 || yy >= gridSize) {
            continue;
        }
        if (grid[yy][xx] == 0) {
            continue;
        }
        if (g_v[yy][xx] == 1) {
            continue;
        }
        dfs(grid, gridSize, gridColSize, xx, yy, gold, result);
    }
    g_v[y][x] = 0;
}

int getMaximumGold(int** grid, int gridSize, int* gridColSize)
{
    int result = 0;
    
    for (int y = 0; y < gridSize; y++) {
        for (int x = 0; x < gridColSize[y]; x++) {
            dfs(grid, gridSize, gridColSize, x, y, 0, &result);
        }
    }
    return result;
}

void test_getMaximumGold(void)
{
    int map[N][3] = {
        { 1, 0, 7 },
        { 2, 0, 6 },
        { 3, 4, 5 },
        { 0, 3, 0 },
        { 9, 0, 20 },
    };
    int *grid[5] = {map[0], map[1], map[2], map[3], map[4]};
    int size = 5;
    int colSize[] = { 3, 3, 3, 3, 3 };
    int result = getMaximumGold(grid, size, colSize);
    printf("%d\n", result);
}